package com.leetcode.partition4;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/11/12 9:04
 */
public class LC375猜数字大小2 {

    public static int getMoneyAmount(int n) {
        //        return memoization(new int[210][210], 1, n);
        return dynamicProgramming(n);
    }

    public static void main(String[] args) {
        System.out.println(getMoneyAmount(10));
    }

    private static int dynamicProgramming(int n) {
        //区间dp，在记忆化搜索寻找最坏情况时，money依赖了[left, i-1]和[i + 1, right]
        //dp[i][j]，在数字范围是[i, j]的情况下最坏的情况和最好的策略时赢得游戏至少需要的钱数量
        int[][] dp = new int[n + 1][n + 1];
        //区间dp遍历规则，因为当前区间依赖了左右区间，如果按照i和j的顺序遍历，则计算结果是错误的
        for (int length = 2; length <= n; length++) {
            for (int left = 1; left + length - 1 <= n; left++) {
                int right = left + length - 1;
                dp[left][right] = 0x3F3F3F3F;
                //枚举[left, right]内的所有的左右子区间，查找最坏情况
                for (int x = left; x < right; x++) {
                    int result = Math.max(dp[left][x - 1], dp[x + 1][right]) + x;
                    dp[left][right] = Math.min(dp[left][right], result);
                }
            }
        }
        Arrays.stream(dp).forEach(val -> System.out.println(Arrays.toString(val)));
        return dp[1][n];
    }

    private static int memoization(int[][] cache, int left, int right) {
        //记忆化搜索，求得[left, right]范围内的猜数字在最坏的情况下，最好的策略下至少需要多少钱才能赢
        if (left >= right) return 0;
        if (cache[left][right] != 0) return cache[left][right];
        int answer = 0x3F3F3F3F;
        for (int i = left; i <= right; i++) {
            //最坏情况下需要多少钱
            int money = Math.max(memoization(cache, left, i - 1), memoization(cache, i + 1, right)) + i;
            //最好的策略下需要的钱
            answer = Math.min(answer, money);
            cache[left][right] = answer;
        }
        return answer;
    }
}
